public class Day9 {
    public static void main(String[] args) {

    }
    //75.颜色分类
    public void sortColors(int[] nums) {
        int n=nums.length;
        int i=0,left=-1,right=n;
        while(i<right) {
            if(nums[i]==1) {
                i++;
            }else if(nums[i]==0) {
                swap(nums,++left,i++);
            }else {
                swap(nums,--right,i);
            }
        }
    }
    public void swap(int[] nums,int i,int j) {
        int tmp = nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
    //200.岛屿数量
    boolean[][] check;
    int count,m,n;
    boolean bool;
    public int numIslands(char[][] grid) {
        m=grid.length;
        n=grid[0].length;
        check = new boolean[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j]=='1'&&check[i][j]==false) {
                    floodfill(grid,i,j);
                }
                bool=false;
            }
        }

        return count;

    }
    public void floodfill(char[][] grid,int i,int j) {
        if(grid[i][j]=='1'&&check[i][j]==false) {
            check[i][j]=true;
        }else {
            return;
        }
        //上，下，左，右
        if(i-1>=0 && grid[i-1][j]=='1'&&check[i-1][j]==false) {
            floodfill(grid,i-1,j);
        }
        if(i+1<m && grid[i+1][j]=='1'&&check[i+1][j]==false) {
            floodfill(grid,i+1,j);
        }
        if(j-1>=0 && grid[i][j-1]=='1'&&check[i][j-1]==false) {
            floodfill(grid,i,j-1);
        }
        if(j+1<n && grid[i][j+1]=='1'&&check[i][j+1]==false) {
            floodfill(grid,i,j+1);
        }
        if(bool==false) {
            count++;
            bool=true;
        }else return;

    }

}
